package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC498 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[] findDiagonalOrder(int[][] matrix) {

            // Check for empty matrices
            if (matrix == null || matrix.length == 0) {
                return new int[0];
            }

            // Variables to track the size of the matrix
            int N = matrix.length;
            int M = matrix[0].length;

            // The two arrays as explained in the algorithm
            int[] result = new int[N * M];
            int k = 0;
            ArrayList<Integer> intermediate = new ArrayList<Integer>();

            // We have to go over all the elements in the first
            // row and the last column to cover all possible diagonals
            for (int d = 0; d < N + M - 1; d++) {

                // Clear the intermediate array every time we start
                // to process another diagonal
                intermediate.clear();

                // We need to figure out the "head" of this diagonal
                // The elements in the first row and the last column
                // are the respective heads.
                int r = d < M ? 0 : d - M + 1;
                int c = d < M ? d : M - 1;

                // Iterate until one of the indices goes out of scope
                // Take note of the index math to go down the diagonal
                while (r < N && c > -1) {

                    intermediate.add(matrix[r][c]);
                    ++r;
                    --c;
                }

                // Reverse even numbered diagonals. The
                // article says we have to reverse odd
                // numbered articles but here, the numbering
                // is starting from 0 :P
                if (d % 2 == 0) {
                    Collections.reverse(intermediate);
                }

                for (int i = 0; i < intermediate.size(); i++) {
                    result[k++] = intermediate.get(i);
                }
            }
            return result;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC498 an = new LC498();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
